package Recursive_search_backtracking_algorithm.Topic1_recursive_algorithm.Topic1_recursive_algorithm;

public class merge_two_sorted_lists {
    //21.合并两个有序链表
    //https://leetcode.cn/problems/merge-two-sorted-lists/description/

    public class ListNode {
        int val;
        Topic1_recursive_algorithm.ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, Topic1_recursive_algorithm.ListNode next) { this.val = val; this.next = next; }
    }
    public Topic1_recursive_algorithm.ListNode mergeTwoLists(Topic1_recursive_algorithm.ListNode list1, Topic1_recursive_algorithm.ListNode list2) {
        if(list1==null ){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        //递归出口理解不到位
        if(list1.val < list2.val){
            list1.next = mergeTwoLists(list1.next,list2);
        }else{
            list2.next = mergeTwoLists(list1,list2.next);
        }
        return list1.val < list2.val ? list1 : list2;
    }
}
